Leetcode刷题记录(Java)

Problem 108 Convert Sorted Array to Binary Search Tree

该问题属于构建树问题,只不过构建的是二叉搜索树,需要满足二叉搜索树的相关条件

主要思路:
题目给出一个已经排好序的int数组用于组建二叉搜索树,根据二叉搜索树的原则,根结点左子树的值都小于根结点,而右子树的值都大于根结点.由于数组已经排序,所以根结点只需要选择中间位置的元素即可.之后递归地构建每个结点的左右子树即可.
该问题的核心在于定界,注意对start和end位置进行重新赋值.

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = subSortedArrayToBST(nums,0,nums.length-1);
        return root;
    }
    public TreeNode subSortedArrayToBST(int[] nums,int start,int end){
        if(start>end){
            return null;
        }
        int middle = (int) Math.ceil((end+start)/2.0);
        TreeNode root = new TreeNode(nums[middle]);
        root.left = subSortedArrayToBST(nums,start,middle-1);
        root.right = subSortedArrayToBST(nums,middle+1,end);
        return root;
    }
}

⭐Problem 110 Balanced Binary Tree

该问题比较经典,要求判断一棵树是否是平衡二叉树,而平衡二叉树的条件是该树中所有结点的左右子树深度之差的绝对值都不大于1.

主要思路:
知道平衡二叉树的定义之后,解决该问题只需要分两步走.

获得每个结点左右子树深度
递归访问所有结点,如遇到有任何结点不满足平衡二叉树条件的,则整棵树不是平衡二叉树.

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        return Math.abs(deep(root.left)-deep(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }
    public int deep(TreeNode root){
        if(root==null)
            return 0;
        return 1+Math.max(deep(root.left),deep(root.right));
    }
}

代码说明:
该代码主要包括两个点:

求深度
递归

对于第一点在deep函数中已经清晰展现,而对于第二点,需要注意的是在判断时始终把我判断条件是以当前结点作为考虑,只考虑当前的情况,否则很容易陷入死循环,就该题来说就是先判断结点的左右子树深度差,之后再递归左子树和右子树.